# -*- coding: utf-8 -*-
"""
Created on Thu Dec 23 14:25:21 2021

@author: Apple
"""

import pandas as pd
import numpy as np
import itertools

"""定义路线的类"""
class Route():
    def __init__(self,point,distance):# 初始化
        self.lp = point               # 左端点
        self.rp = point               # 右端点
        self.dis = distance           # 该线路的距离
        self.alp = [point]            # 该线路上的所有点
    
    def insert_avl(self,a,b):
        lp = self.lp
        rp = self.rp
        point = self.alp
        if a == rp:
            return 1
        if b == lp:
            return -1

"""读取excel文件"""
def read_excel(file_name):
    with open(file_name,'rb') as f:
        df = pd.read_excel(file_name,index_col=0)
    f.close()
    return df

"""输入基点（出发点）以及距离矩阵，生成初始路线，distance_mat为DataFrame"""
def init_route_generation(point_set,bp,distance_mat):
    df = distance_mat
    init_route = []
    for i in point_set:
        distance = df.loc[i][bp]
        item = [i,distance]
        init_route.append(item)
    return init_route

"""生成节约路径"""
def saving_route(point_set,distance_mat,init_route):
    curve_set = {} # 存储两个地点之间的路线长度
    """itertools.permutations 排列,itertools.combinations 组合"""
    for i in itertools.permutations(point_set, 2):
        distance = distance_mat.loc[i[0]][i[1]]
        a = [x[1] for x in init_route if x[0]==i[0]]
        b = [x[1] for x in init_route if x[0]==i[1]]
        saving_distance = round(a[0]+b[0]-distance,3)
        curve_set[i] = saving_distance
    curve_order=sorted(curve_set.items(),key=lambda x:x[1],reverse=True) # 返回从大到小排列的路程节约值
        
    return curve_order

"""插入路线，生成最终路径"""
"""判断线路(i,j)能否插入的条件为：1、点i,j不在一条线路上 2、点i和j均与基点相邻"""
def insert_route(route_set,a,b,dis_save):
    list_a = []
    list_b = []
    for i in route_set:
        if Route.insert_avl(i,a,b)==1:
            list_a.append(i)
        elif Route.insert_avl(i,a,b)==-1:
            list_b.append(i)
        else:
            continue
    
    if list_a !=[] and list_b != []:
        list_a[0].rp = list_b[0].rp
        list_a[0].alp += list_b[0].alp
        list_a[0].dis = round(list_a[0].dis+list_b[0].dis - dis_save,3)
        route_set.remove(list_b[0])
    
    return list_a

"""最终路径生成"""
def get_final_route(curve_set,route_set):
    while len(route_set) !=1:
        for i in curve_set:
            a = i[0][0]
            b = i[0][1]
            dis_save = i[1]
            insert_route(route_set, a, b, dis_save)
    
    return route_set

"""主程序"""
def main(base_point,file_name): # 输入基点，距离矩阵
    
    """读取距离文件"""
    df = read_excel(file_name)
    point_set = list(df.index)  # 点集合
    point_set.remove(base_point) # 去掉基点
    
    """生成初始路线，即单个点到基点的路线"""
    init_route = init_route_generation(point_set,base_point,df) # 不包括基点本身
    # print(init_route)
    
    """生成所有的路线弧"""
    curve_set = saving_route(point_set, df,init_route) # 求出所有线路弧以及对应的节约值
    # print(curve_set)
    
    """创建路线的类"""
    route_set = []
    for i in init_route:
        route = Route(i[0],2*i[1])
        route_set.append(route)
    
    """生成最终路线"""
    final_route = get_final_route(curve_set, route_set)
    route_express = [base_point]+final_route[0].alp + [base_point] # 路线表达
    route_dis = final_route[0].dis # 距离
    
    return route_express,route_dis

if __name__ == "__main__":
    base_point = 'C'
    file_name = r'Data\dismat.xlsx'
    route_express,route_dis = main(base_point,file_name)